#include <cassert>
#include <vector>
#include <functional>
#include "graphIO.h"
#include "sequenceIO.h"
#include "utils.h"
#include "Timer.h"
#include "MRandSet.h"
#include "MStack.h"
#include "degeneracy.h"

namespace ListPlex{
    using VType = int;  
    using PlexStack = Stack<VType>;
    using VtxSet = RandSet<VType>;
    using Graph = graph<VType>;
    template <typename MaximalityChecker, typename Emitor, typename VType>
    struct KplexListor
    {
        Graph subg;
        MaximalityChecker *plexMaxChecker;
        Emitor *emitor;
        
        int *neiInP;
        int *neiInG;
        PlexStack *plexStack;
        VtxSet *cand;
        VtxSet *excl;

        // The last 5 parameters are runtime data
        KplexListor(Graph &_subg,MaximalityChecker *_plexMaxChecker, Emitor*_emitor,
                    PlexStack *_plex, VtxSet *_cand, VtxSet *_excl, int *_neiInP, int *_neiInG) 
        :subg(_subg),plexMaxChecker(_plexMaxChecker),emitor(_emitor)
        {
            plexStack = _plex;
            cand = _cand;
            excl = _excl;
            neiInP = _neiInP;
            neiInG = _neiInG;
        }

        KplexListor(const KplexListor& o)
        :subg(o.subg),plexMaxChecker(o.plexMaxChecker),emitor(o.emitor)
        {
            plexStack = new PlexStack(*(o.plexStack));
            cand = new VtxSet(*(o.cand));
            excl = new VtxSet(*(o.excl));

            neiInP = new int[subg.n];
            memcpy(neiInP, o.neiInP,sizeof(int)*subg.n);
            neiInG = new int[subg.n];
            memcpy(neiInG, o.neiInG, sizeof(int)*subg.n);
        }

        ~KplexListor()
        {
            delete plexStack;
            delete cand;
            delete excl;
            delete[] neiInP;
            delete[] neiInG;
        }

        inline bool isAdj(VType v1, VType v2)
        {
            if(subg.V[v1].degree>subg.V[v2].degree)
                std::swap(v1, v2);
            return binary_search(subg.V[v1].Neighbors, subg.V[v1].Neighbors + subg.V[v1].degree, v2);
        }

        //---only change the plex stack
        KplexListor* pushToPlex(VType v)
        {
            plexStack->push(v);
            for (int i = 0; i < subg.V[v].degree; i++)
            {
                VType nei = subg.V[v].Neighbors[i];
                neiInP[nei]++;
            }
            return this;
        }

        VType popPlex()
        {
            VType u = plexStack->top();
            plexStack->pop();
            for (int i = 0; i < subg.V[u].degree; i++)
            {
                VType nei = subg.V[u].Neighbors[i];
                neiInP[nei]--;
            }
            return u;
        }
        //change plex stack and cand
        KplexListor* candToPlex(VType v)
        {
            plexStack->push(v);
            cand->remove(v);
            for (int i = 0; i < subg.V[v].degree; i++)
            {
                VType nei = subg.V[v].Neighbors[i];
                neiInP[nei]++;
            }
            return this;
        }

        VType plexToCand()
        {
            assert(plexStack->sz > 0);
            VType u = plexStack->top();
            cand->add(u);
            plexStack->pop();
            for (int i = 0; i < subg.V[u].degree; i++)
            {
                VType nei = subg.V[u].Neighbors[i];
                neiInP[nei]--;
            }
            return u;
        }

        //Only change the cand set
        KplexListor* removeFrCand(VType u)
        {
            assert(cand->contains(u));
            cand->remove(u);
            for (int i = 0; i < subg.V[u].degree; i++)
            {
                VType nei = subg.V[u].Neighbors[i];
                neiInG[nei]--;
            }
            return this;
        }

        KplexListor* removeFrExcl(VType u)
        {
            excl->remove(u);
            return this;
        }

        KplexListor* addToExcl(VType u)
        {
            shortprompt("Add %d to excl\n", u);
            excl->add(u);
            return this;
        }

        KplexListor* addToCand(VType u)
        {
            assert(!cand->contains(u));
            cand->add(u);
            for (int i = 0; i < subg.V[u].degree; i++)
            {
                VType nei = subg.V[u].Neighbors[i];
                neiInG[nei]++;
            }
            return this;
        }
        //check if plex+u is a k-plex
        bool canFormPlex(VType u)
        {
            //assert(cand->contains(u) || excl->contains(u));
            if (neiInP[u] + k < plexStack->sz + 1)
            {
                return false;
            }
            for (int i = 0; i < plexStack->sz; i++)
            {
                VType v = plexStack->members[i];
                assert(v != u);
                if (neiInP[v] + k == plexStack->sz && !isAdj(v, u))
                { //v is saturated by v,u are not neighbors
                    return false;
                }
            }
            return true;
        }

        void checkAsMaxPlex()
        {
            //move to plex, but cand still keeps these vertices
            cand->for_each([&](VType u) {
                pushToPlex(u);
            });

            int num_excl = 0;
            excl->for_each([&](VType u) {
                if (!canFormPlex(u))
                { //Ele in exclusive set which is not changed
                    num_excl++;
                }
            });
            if(excl->size() == num_excl)
            {
                prompt("G is a max k-plex\n");
                if (plexMaxChecker->isMaximal(plexStack->members, plexStack->sz, neiInP))
                {
                    emitor->emitPlex(plexStack->members, plexStack->sz);
                }
            }else{
                    prompt("G is not a max k-pex\n");
            }
            //recover
            for (int i = 0; i < cand->sz; i++)
            {
                popPlex();
            }
        }

        void branchInPlex(VType pivot)
        {
            assert(!cand->contains(pivot));            
            int tol = k + neiInP[pivot] - plexStack->sz;
            prompt("tol %d \n",tol);
            assert(tol > 0);
            int addlist[K_LIMIT];
            int sz = 0;
            //Filter cand and find
            prompt("");
            for (VtxSet::TIndex i = 0; i < cand->size(); i++)
            {
                VType u = (*cand)[i];
                if (!isAdj(pivot, u))
                {
                    addlist[sz++] = u;
                    shortprompt("Add %d, ", u);
                }
                if (sz == tol)
                {                    
                    break;
                }
            }
            shortprompt("to addlist\n");
            if (sz != tol){
            printf("Neibo [%d] :", pivot);
                for (int i = 0; i < subg.V[pivot].degree; i++)
                    printf("%d ", subg.V[pivot].Neighbors[i]);
            printf("\n");
            }
            assert(sz == tol);
            //There are at most tol+1 branches.
            //br0;
            VType v2delete = addlist[0];
            prompt("Br0: remove %d to exclusive\n", v2delete);
            removeFrCand(v2delete);
         
            excl->add(v2delete);
            listByCase();
            excl->remove(v2delete);
            addToCand(v2delete);

            //Proceed br1 in [1,tol-1); there are at least 2 branches
            //add in addlist[0,...,br), remove addlist[br].
            VType v2add;
            vector<VType> _tmp;
            Stack<VType> _rec_cand(cand->size()); //use stack to optimize
            Stack<VType> _rec_excl(excl->size());            
            int movals = 0; // recording the number of vertices pushing into kplex

            //start from the 1st br.
            int br = 1;
            for (; br < tol; br++)
            {
                prompt("Br%d \n",br);
                v2add = addlist[br - 1];
                v2delete = addlist[br];
                //if v2add has not been reduced by feasibility condition, i.e., v2add in cand
                //or the graph size is above lb. stop
                if (cand->contains(v2add) || plexStack->sz + cand->size() >= lb) 
                {
                    //move v2 add to plex and update cand
                    candToPlex(v2add);
                    movals +=1; //mark the number of pushed vertices
                    cand->for_each([&](VType u) {
                        if (!canFormPlex(u))
                        {
                            _tmp.emplace_back(u);
                        }
                    });
                    for (auto u : _tmp)
                    {
                        removeFrCand(u);
                        _rec_cand.push(u);
                    }
                    _tmp.clear();
                    //update exclusive
                    excl->for_each([&](VType u) {
                        if (!canFormPlex(u))
                        {
                            _tmp.emplace_back(u);
                        }
                    });
                    for (auto u : _tmp)
                    {
                        excl->remove(u);
                        _rec_excl.push(u);
                    }
                    if (cand->contains(v2delete))
                    {
                        //if v2delete is still in cand, remove it ;
                        removeFrCand(v2delete);
                        excl->add(v2delete);
                        listByCase();
                        excl->remove(v2delete); //recover the remove vertices
                        addToCand(v2delete);
                    }
                    else
                    {
                        listByCase();
                    }
                }
                else
                {
                    //no need to branch more beacuse the [0,br-1th] in cand cannot form a k-plex
                    break;
                }
            }
            //The last (tolth) branch.
            if (br == tol && cand->contains(addlist[br - 1]) && plexStack->sz + cand->size() >= lb)
            {
                showContext();
                prompt("Br%d (the last)\n",br);
                v2add = addlist[tol - 1];
                prompt("%d cand to plex\n", v2add);
                candToPlex(v2add); //all vertices in addlist has moved to plex        
                movals += 1;
                //--------update cand---------
                _tmp.clear();
                cand->for_each([&](VType v) {
                    if (!isAdj(v, pivot))
                    {
                        _tmp.emplace_back(v); // mark as being removed from cand
                        //exclusive->add(v);  // not necessarily need to exclusive
                    }
                    else if (!canFormPlex(v))
                    { //
                        _tmp.emplace_back(v);
                    }
                });
                prompt("update cand:");
                for (auto u : _tmp)
                { //remove from cand
                    removeFrCand(u);
                    shortprompt("remove %d fr cand, ", u);
                    _rec_cand.push(u); //for recovery
                }
                shortprompt("\n");
                //-----------update exclusive------
                _tmp.clear();
                excl->for_each([&](VType v) {
                    if (!canFormPlex(v))
                    {
                        _tmp.emplace_back(v);
                    }
                });
                prompt("update excl:");
                for (auto u : _tmp)
                {
                    excl->remove(u);
                    shortprompt("remove %d fr excl, ", u);
                    _rec_excl.push(u);
                }
                shortprompt("\n");
                
                listByCase();
            }
            //recover cand and excl
            //pop the last br vertices
            for (int i = 0; i < movals; i++)
            {
                plexToCand();
            }
            _rec_cand.for_each([&](VType u) { addToCand(u); });
            _rec_excl.for_each([&](VType u) { excl->add(u); });
            //br[tol]
        }

        inline KplexListor* updateCand(Stack<VType>& _rec){
            cand->for_each([&](VType u) {
                if (!canFormPlex(u))
                {
                    _rec.push(u);
                }
            });
            _rec.for_each([&](VType u) {
                removeFrCand(u);
                shortprompt("remove %d fr cand,", u);
            });
            return this;
        }

        inline KplexListor* updateExcl(Stack<VType>& _rec){
            excl->for_each([&](VType u) {
                if (!canFormPlex(u))
                    _rec.push(u);
            });
            _rec.for_each([&](VType u) {
                excl->remove(u);
                shortprompt("remove %d fr excl,", u);
            });
            return this;
        }
        //start from select pivot into the solution
        void branchBySelection(VType pivot){
            assert(cand->contains(pivot));
            //first branch, move pivot to the solution
            candToPlex(pivot);
            prompt("%d from Cand to Plex \n",pivot);
            prompt("update: ");
            Stack<VType> _rec_cand(cand->sz);
            Stack<VType> _rec_excl(excl->sz);
            updateCand(_rec_cand)->updateExcl(_rec_excl);
            listByCase();

            prompt("Recover \n");
            VType _p = plexToCand();
            assert(pivot == _p);
            _rec_cand.for_each([&](VType u) {
                addToCand(u);
            });
            _rec_excl.for_each([&](VType u) {
                excl->add(u);
            });
            _rec_cand.destory();
            _rec_excl.destory();
        }
        void branchInCand(VType pivot)
        {
            //In the first branch, select pivot
            branchBySelection(pivot);

            //In the second branch, remove pivot
            removeFrCand(pivot)->addToExcl(pivot);
            listByCase();
            removeFrExcl(pivot)->addToCand(pivot);
        }

        void findPivot(int& minnei,VType& pivot){
            //find pivot
            minnei = INT_MAX;
            auto maxswap = [&](VType u) {
                if (neiInG[u] < minnei)
                {
                    minnei = neiInG[u];
                    pivot = u;
                }
            };
            plexStack->for_each(maxswap);
            cand->for_each(maxswap);
        }

        void listByCase()
        {
            showContext();
            if (plexStack->sz + cand->sz < lb){
                prompt("Cand %d + exlusive %d small than lb\n", plexStack->sz, cand->size());
                return;
            }
            if (cand->sz == 0 && excl->sz == 0)
            {
                prompt("cand and exclusive are empty\n");
                if (true == plexMaxChecker->isMaximal(plexStack->members, plexStack->sz, neiInP))
                {
                    emitor->emitPlex(plexStack->members, plexStack->sz);
                }
                return;
            }
            if (cand->sz == 0)
            {
                prompt("Empty cand but unempty exclusive\n");
                return;
            }
            //find pivot
            int minnei;VType pivot;
            findPivot(minnei, pivot);
            prompt("Pivot : %d. NeiInG[pivot] %d\n", pivot, minnei);
            //TODO: for better branching prediction:change to switch
            if (minnei >= plexStack->sz + cand->sz - k)
            {
                prompt("P+C is a k-plex. Chek G as a Kplex\n");
                checkAsMaxPlex();              
            }
            else if (!cand->contains(pivot)) //in plex
            {
                prompt("%d is in Plex. Branch in K-plex\n", pivot);
                if((plexStack->sz+cand->sz)>GRAIN_SIZE)branchInPlex(pivot);
                else branchInPlex(pivot);
            }
            else
            {
                prompt("%d is in Cand. Branch in Cand\n", pivot);
                if((plexStack->sz+cand->sz)>GRAIN_SIZE)branchInCand(pivot);
                else  branchInCand(pivot);
            }
        }

        void printContextInfo(){
            printf("\n\n[DEPTH]: %d\n", plexStack->sz);
            printf("PLEX:");
            plexStack->for_each([](VType v){printf("%d ",v);});
            printf("\nCAND:");
            cand->for_each([](VType v){printf("%d ",v);});
            printf("\nEXCLUSIVE:");
            excl->for_each([](VType v){printf("%d ",v);});
            printf("\n");
            
            for (int i = 0; i < subg.n; i++)
                printf("[%d]%d:%d ", i, neiInP[i], neiInG[i]);
            printf("\n");
        }
    }; //end of KplexListor
}